#include <iostream>
#include <Graph.hpp>
#include <map>
#include <set>

using namespace std;

class Solution
{
public:
    void CloneNodeAndSaveMap(Node *node, map<Node *, Node *> &mp)
    {
        if (node == nullptr)
        {
            return;
        }
        if (mp.find(node) != mp.end())
        {
            return;
        }
        mp[node] = new Node(node->val);
        for (auto n : node->neighbors)
        {
            CloneNodeAndSaveMap(n, mp);
        }
    }
    void Connect(Node *nodeBase, map<Node *, Node *> &mp)
    {
        if (nodeBase == nullptr)
        {
            return;
        }
        // 除去只包含一个点的情况,节点不可能不包含邻居节点
        // if (nodeBase->neighbors.size() == 0)
        //{
        //    return;
        //}
        Node *Nnode = mp[nodeBase];
        if (Nnode->neighbors.size() != 0)
            return;
        Nnode->neighbors.resize(nodeBase->neighbors.size());
        for (int i = 0; i < nodeBase->neighbors.size(); i++)
        {
            Nnode->neighbors[i] = mp[nodeBase->neighbors[i]];
        }
        for (int i = 0; i < nodeBase->neighbors.size(); i++)
        {
            Connect(nodeBase->neighbors[i], mp);
        }
    }
    Node *cloneGraph(Node *node)
    {
        if (node == nullptr)
            return nullptr;
        if (node->neighbors.size() == 0)
            return new Node(node->val);
        map<Node *, Node *> mp;
        CloneNodeAndSaveMap(node, mp);
        Connect(node, mp);
        return mp[node];
    }
};

int main()
{
    cout << "Code133" << endl;
    Solution s;
    vector<vector<int>> edges = {
        {1, 2},
        {2, 3},
        {3, 4},
        {1, 4}};
    Node *node = CreateNodeFromLinkedIDList(edges);
    Node *clone = s.cloneGraph(node);
    return 0;
}